package com.gitee.ywj1352.算法.week02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 全排列 {


    /**
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        boolean[] status = new boolean[nums.length];
        List<List<Integer>> solution = new ArrayList<>();
        helper(nums, status, 0, new ArrayList<>(), solution);
        return solution;

    }


    public static void helper(int[] nums, boolean[] status, int level, List<Integer> res, List<List<Integer>> solution) {
        if (level == nums.length) {
            solution.add(res);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (status[i]) continue;
            boolean[] booleans = Arrays.copyOf(status, status.length);
            List<Integer> integers = new ArrayList<>(res);
            integers.add(nums[i]);
            booleans[i] = true;
            helper(nums, booleans, level + 1, integers, solution);

        }
    }

    public static List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> solution = new ArrayList<>();
        helper2(nums, 0, new ArrayList<>(), solution);
        return solution;

    }


    public static void helper2(int[] nums, int level, List<Integer> res, List<List<Integer>> solution) {
        if (level == nums.length) {
            solution.add(new ArrayList<>(res));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (res.contains(nums[i])) continue;
            res.add(level, nums[i]);
            helper2(nums, level + 1, res, solution);
            res.remove(level);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(permute2(arr));
    }
}
